The Lenstra-Lenstra-Lov\'asz (LLL) algorithm is the most practical latticereduction algorithm in digital communications. In this paper, several variantsof the LLL algorithm with either lower theoretic complexity or fixed-complexityimplementation are proposed and/or analyzed. Firstly, the $O(n^4\log n)$theoretic average complexity of the standard LLL algorithm under the model ofi.i.d. complex normal distribution is derived. Then, the use of effective LLLreduction for lattice decoding is presented, where size reduction is onlyperformed for pairs of consecutive basis vectors. Its average complexity isshown to be $O(n^3\log n)$, which is an order lower than previously thought. Toaddress the issue of variable complexity of standard LLL, two fixed-complexityapproximations of LLL are proposed. One is fixed-complexity effective LLL,while the other is fixed-complexity LLL with deep insertion, which is closelyrelated to the well known V-BLAST algorithm. Such fixed-complexity structuresare much desirable in hardware implementation since they allow straightforwardconstant-throughput implementation.
展开▼
